package codetop.bytedance.T958;

import util.TreeNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: 18362
 * @Create: 2022-09-17 21:47:55 星期六
 */
class Solution {

    private int maxNum = 0;

    public boolean isCompleteTree(TreeNode root) {
        Set<Integer> vis = new HashSet<>();
        tranverse(root, 0, vis);
        for (int i=0; i <= maxNum; ++i) {
            if (!vis.contains(i))
                return false;
        }
        return true;
    }

    private void tranverse(TreeNode root, int num, Set<Integer> vis) {
        if (root == null)
            return;
        vis.add(num);
        maxNum = Math.max(maxNum, num);
        tranverse(root.left, num * 2 + 1, vis);
        tranverse(root.right, num * 2 + 2, vis);
    }
}